Distributed processing networks are gaining increasing importance in our information-based society. FIG. 1 depicts a network topology of a simple computer network. The network 100 comprises a plurality of routers 104a–g, a transit network 108, and a stub network 112, all interconnected by links 116a–i. As will be appreciated, a router is a device connecting two or more networks that routes incoming data or packets to an appropriate network/node; a transit network is a network containing more than one router; a stub network is a network containing only one router; and a link is a communication channel between two or more nodes. Each of the routers is typically attached to a link via one or more interfaces, such as interfaces 120a–n. The simple network of FIG. 1 is divided into two protocol regions with the dashed line 124 being the boundary between the two regions. Router 104c is located on the boundary 124 and is typically referred to as an area border router while the other routers 104a–b and d–g are not area border routers. One or more protocol regions are often autonomous systems. An autonomous system is a collection of networks controlled by a single administrative authority.
In a packet-switched network, the technique used to route a packet through interconnected networks depends on the routing protocol. Most protocols fall into one of two categories, distance-vector algorithms (which make routing path decisions based on a number of router hops a packet traverses en route from the source network to the destination network) and link-state algorithms (which use link state advertisement or LSA (containing the names and various cost metrics of a router's neighbors in a defined area) to keep routers informed about links in the network). Rather than storing the next hop (which is the case with distance-vector algorithms), link-state algorithms store the information needed to generate routing paths. Examples of router protocols using distance-vector algorithms include EIGRP, RIP and RIP-2 and using link-state algorithms include Open Shortest Path First or OSPF, OSI's IS—IS, and Netware's Link Service's Protocol (NLSP).
Routers and other network components are typically managed using a network management system. Network management systems perform network maintenance, identify possible security problems in the network, locate equipment, module, subassembly, and card failures, locate circuit outages, monitor levels of performance (e.g., bit error rates or BERs, loss of synchronization, etc.) and permit rapid and accurate quantification of network usage and traffic levels. Examples of network management systems used for performing the foregoing tasks include Hewlett-Packard's OpenView™, IBM's Netview™, and Digital Equipment Corporation's Enterprise Management Architecture or EMA™.
For optimal operation of network management systems, an accurate, detailed map of the network or OSI layer 3 topologies is commonly required. Such a map not only facilitates operation of the network management system but also permits newly attached hosts to be properly located and configured for the network (to avoid adversely impacting network performance) and existing hosts to be properly located for the newly attached host. In common practice, a detailed map of the network's topology is, in whole or part, unavailable to network management personnel. This can be due to poor record keeping, the sheer size and complexity of some networks, and the lack of central management of a network, such as where a network includes a number of autonomous systems or enterprises.
The discovery of network topology is not a simple task for network administrators. Simple Network Management Protocol or SNMP algorithms for discovering automatically network layer (or OSI Layer 3) topology are used in many network management tools. Such algorithms use only basic IP primitive functionality and are very slow. Typically, the techniques flood the network with ping commands for every possible host or interface address, which can not only interfere with the operational efficiency of the network but also require an extensive use of computational resources to analyze the received information. Although vendor-specific solutions exist, they typically rely on the vendor-specific extensions to the standard SNMP MIBs that are not useful in a typical multi-vendor network. Other known network topology discovery algorithms use the Managed Information Base on MIB information stored by all routing protocols. Every router must be contacted by this algorithm. MIB information is, of necessity, the lowest common denominator-type of information available on all routers, regardless of routing protocol, and cannot contain more information than provided by the weakest link, namely distance-vector algorithms (i.e., information relating to the nearest neighbor only). Contacting every router is problematical because any routers not running SNMP cannot provide the MIB information.